This is a randomized study evaluating alternative immunization strategies in patients with metastatic melanoma. Patients will be immunized with 1 of the P1-P3 or P5 peptides (100ug). IL-12 will be given subcutaneously at 30 (Tier 1), 100 (Tier 2), or 300 (Tier 3) ng/kg at a location adjacent to the peptide. All patients will also be vaccinated with HLA- A2 presented recall antigen (influenza A matrix (Flu M1 58-66: GILGFVFTL) peptide at a contralateral site.